// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P() // Wait
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V() // Signal
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

// Dummy functions -- so we can compile our later assignments 
// Note -- without a correct implementation of Condition::Wait(), 
// the test case in the network assignment won't work!
Lock::Lock(char* debugName) {
	name = debugName;
	busy = false;
	ownerThread = NULL;
	waitingQueue = new List();
}
Lock::~Lock() {
	delete waitingQueue;
}
void Lock::Acquire() {
	//disable interupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts

	if (ownerThread == currentThread) { // I am lock owner
		DEBUG('L', "%s: %s attempted to acquire lock but he is already the owner.\n", name, currentThread->getName());
		//restore interupts + return;
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	if (!busy) { // lock is availible
		DEBUG('L', "%s: Lock is now busy.\n", name);
		//make if BUSY
		busy = true;
		//make myself the lock owner
		DEBUG('L', "%s: %s now owns this Lock.\n", name, currentThread->getName());
		ownerThread = currentThread;
	}
	else { // lock not availible
		DEBUG('L', "%s: %s added to the waitingQueue and asleep.\n", name, currentThread->getName());
		//add myself to the queue
		waitingQueue->Append((void *)currentThread);
		currentThread->Sleep();
	}
}
void Lock::Release() {
	//disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	
	if (ownerThread != currentThread) { // I'm not the lock owner
		//print error message
		DEBUG('L', "%s: Error non-owner %s trying to release Lock.\n",name,
	       currentThread->getName());
		//restore interrupts + return
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	
	//remove 1 lock from the lock's wait queue
	Thread* nextThread = (Thread *)waitingQueue->Remove();
	if (nextThread) { // A thread is waiting
		//put them in the ready queue in the ready state
		DEBUG('L', "%s: %s removed from waitingQueue and awoken.\n", name, nextThread->getName());
		scheduler->ReadyToRun(nextThread);
		//make them in the lock owner
		ownerThread = nextThread;
	}
	else { // waiting queue is empty
		DEBUG('L', "%s: Lock is now free.\n", name);
		//make lock FREE
		busy = false;
		//clear lock ownership
		ownerThread = NULL;
	}
	//restore interrupts
	(void) interrupt->SetLevel(oldLevel);
}
bool Lock::isHeldByCurrentThread() {
	return (ownerThread == currentThread);
}

Condition::Condition(char* debugName) {
	name = debugName;
	waitingLock = NULL;
	waitingQueue = new List();
}

Condition::~Condition() {
	delete waitingQueue;
}

void Condition::Wait(Lock* conditionLock) { 
	//disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	
	if (conditionLock == NULL) {
		//print msg
		DEBUG('C', "%s: Condition Wait: null conditionLock arg\n", name);
		//restore interrupts + return
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	if (waitingLock == NULL) {
		// This is first thread calling wait
		waitingLock = conditionLock;
		DEBUG('C', "%s: %s is now the waitingLock.\n", name, waitingLock->getName());
	}
	
	if (waitingLock != conditionLock) {
		//print error msg
		DEBUG('C', "%s: %s requested wait but we are currently busy with another lock %s\n", name, conditionLock->getName(),
			waitingLock->getName());
		//restore interrupts + return
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	// ok to wait
	conditionLock -> Release(); // exited the monitor
	// add myself to C.V. wait Queue
	waitingQueue->Append((void *)currentThread);
	DEBUG('C', "%s: %s added to waitingQueue and is asleep.\n", name, currentThread->getName());
	currentThread -> Sleep();
	conditionLock->Acquire();
	//restore interrupts
	(void) interrupt->SetLevel(oldLevel);
}
void Condition::Signal(Lock* conditionLock) {
	//disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	
	// If no waiters, restore interrupts + return
	if (waitingLock != conditionLock) { 
		//print msg
		DEBUG('C', "%s: %s requested signal but is not the waitingLock\n", name, conditionLock->getName());
		//restore interrupts + return
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	
	// wake up 1 waiter
	//remove 1 thread from condition wait queue
	Thread* nextThread = (Thread *)waitingQueue->Remove();
	if (nextThread) { // A thread is waiting
		//put them in the ready queue in the ready state
		DEBUG('C', "%s: %s removed from waitingQueue and awoken.\n", name, nextThread->getName());
		scheduler->ReadyToRun(nextThread);
	}
	
	if (waitingQueue->IsEmpty()) { // no more waiting threads
		waitingLock = NULL;
		DEBUG('C', "%s: Condition Variable is now free.\n", name);
	}
	//restore interrupts + return
	(void) interrupt->SetLevel(oldLevel);
}
void Condition::Broadcast(Lock* conditionLock) {
	while (!waitingQueue->IsEmpty()) { // there are waiters
		Signal(conditionLock);
	}
}
